package com.moyoutian.sort;

import com.moyoutian.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 快排练习
 */
public class QuickSort4 {
    public static void main(String[] args) {

        test();

    }

    /**
     * 测试程序
     */
    public static void test() {
        // 测试次数
        int testCount = 50000;
        for (int i = 0; i < testCount; i++) {
            test(ArrayUtils.getIntAr());
        }
    }

    public static void test(int[] ints) {
        int[] copy_ints_sort = Arrays.stream(ints).sorted().toArray();
        sort(ints);
        if (!Arrays.equals(copy_ints_sort, ints)) {
            System.out.println("QuickSort.test ");
        }
    }

    private static void sort(int[] ints) {
        if (ints.length > 1) {
            sort(ints, 0, ints.length - 1);
        }
    }

    private static void sort(int[] ints, int left, int right) {
        // 如果左下标大小于又下标就处理
        if (left < right) {
            int tempNumber = ints[right];
            int tempLeft = left;
            int tempRight = right;

            while (left < right) {
                while (ints[left] < tempNumber && left < right) {
                    left++;
                }
                while (ints[right] >= tempNumber && left < right) {
                    right--;
                }
                ArrayUtils.swap(ints, left, right);
            }
            // 最开始的记录交换
            ArrayUtils.swap(ints, tempRight, right);

            //左边排序
            if (tempLeft < right - 1) {
                sort(ints, tempLeft, right - 1);
            }
            //右边排序
            if (right + 1 < tempRight) {
                sort(ints, right + 1, tempRight);
            }
        }
    }
}
